/*
 * @lc app=leetcode.cn id=75 lang=swift
 *
 * [75] 颜色分类
 像这种一次遍历的都需要采用多指针的方法；
 */

// @lc code=start
class Solution75 {
    // 颜色分类
    // 即使是用最好的排序也是nlogn
    // 但是我可以用一遍扫描法进行排序
    // 将0 做移动，将2想右移动
    func sortColors(_ nums: inout [Int]) {
        var left = 0
        var right = nums.count - 1
        var cur = 0
        while cur <= right {
            let tmp = nums[cur]
            if tmp == 0 {
                nums[cur] = nums[left]
                nums[left] = tmp
                left += 1
                cur += 1
            } else if tmp == 2 {
                nums[cur] = nums[right]
                nums[right] = tmp
                right -= 1
            } else {
                cur += 1
            }
        }
    }
    static func test() {
        let solution = Solution75()
        var nums: [Int] = [2, 0, 2, 1, 1 ,0]
        
        solution.sortColors(&nums)
        print(nums)
    }
}
// @lc code=end

